// 快速幂
//
#include <stdio.h>

// 朴素算法
// 只考虑b>=0的情况
int pow_naive(int a, int b) {
    int ret = 1;

    while (b--) {
        ret *= a;
    }

    return ret;
}

int pow_fast(int a, int b) {
    int ret = 1;
    int base = a;

    while (b) {
        if (b & 1) { // 最低位为1, 比如 1101最右边的1
            ret *= base;
        }
        b >>= 1;
        base *= base;
    }
    return ret;
}

// http://acm.hdu.edu.cn/showproblem.php?pid=1061
// N^N % 10   1 <= N <= 1,000,000,000
// a^b % c = (a % c)^b % c
int pow_fast_tpl(int a, int b, int c) {
    int ret = 1;
    int base = a % c;

    while (b) {
        if (b & 1) {
            ret = (ret * base) % c;
        }
        base = (base * base) % c;
        b >>= 1;
    }

    return ret;
}

int main(int argc, char const *argv[])
{
    printf("%d\n", pow_naive(2, 10));
    printf("%d\n", pow_fast(2, 10));
    printf("%d\n", pow_fast_tpl(99, 99, 10));
    return 0;
}
